package 数组.排序算法;

import java.util.Arrays;

public class 希尔排序序 {
    public static void main(String[] args) {

        int[] sz = {1, 5, 9, 7, 5, 2, 8, 9};
//        shellSort(sz);
        xrpx(sz);
        System.out.println(Arrays.toString(sz));
    }

    /**
     * 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
     *
     * 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
     * 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
     * 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位
     *
     * 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，
     * 再对全体记录进行依次直接插入排序。
     *
     * 算法步骤：
     * （1）选择一个增量序列t1，t2，…，tn，其中，tn=1；一般情况"我们可以用一个序列来表示增量：{n/2,(n/2)/2...1}，每次增量都/2"
     * （2）按增量序列个数k，对序列进行k 趟排序；
     * （3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
     * 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
     * @param sz
     */
    public static void xrpx(int[]sz){
        for (int i = sz.length/2; i >0 ; i/=2) {//对数组进行分割成多个子序列 同时记录增量（i）
            for (int j = i; j <sz.length ; j++) {//控制每次数组分割后插入数据的个数
                int zz = sz[j];
                int k = j;
                for (; k-i >=0 ; k= k-i) {//循环判断插入数据的位置
                    if (sz[k-i]>zz){
                        sz[k] = sz[k-i];
                    }else {
                        break;
                    }
                }
                sz[k] =zz;
            }
        }
    }
    public static void shellSort(int[] arrays) {


        //增量每次都/2
        for (int step = arrays.length / 2; step > 0; step /= 2) {

            //从增量那组开始进行插入排序，直至完毕
            for (int i = step; i < arrays.length; i++) {

                int j = i;
                int temp = arrays[j];

                // j - step 就是代表与它同组隔壁的元素
                while (j - step >= 0 && arrays[j - step] > temp) {
                    arrays[j] = arrays[j - step];
                    j = j - step;
                }
                arrays[j] = temp;
            }
        }


    }
}
